package pers.whj.util.tree;

import pers.whj.util.InvalidParamException;
import pers.whj.util.NoSuchElementException;
import pers.whj.util.list.QueueList;
import pers.whj.util.list.Stack;

public abstract class AbstractTree<T> implements Tree<T> {
    protected Node<T> root;
    protected int size;

    protected static class Node<T> {
        protected T data;
        protected Node<T> left;
        protected Node<T> right;

        public Node(T data) {
            this.data = data;
        }

        public Node(T data, Node<T> left, Node<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public void reset() {
            this.data = null;
            this.left = null;
            this.right = null;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int height() {
        return height(this.root);
    }

    @Override
    public T root() {
        return this.root == null ? null : root.data;
    }

    @Override
    public T child(TreePath treePath) {
        Node<T> node = get(treePath);
        return node == null ? null : node.data;
    }

    @Override
    public T child(String treePath) {
        Node<T> node = get(treePath);
        return node == null ? null : node.data;
    }

    @Override
    public T parent(T data) {
        Node<T> node = search(this.root, data);
        checkNode(node);
        node = parentOf(node);
        return node == null ? null : node.data;
    }

    @Override
    public void set(T oldData, T newData) {
        Node<T> node = search(this.root, oldData);
        checkNode(node);
        node.data = newData;
    }

    @Override
    public void set(TreePath treePath, T data) {
        Node<T> node = get(treePath);
        checkNode(node);
        node.data = data;
    }

    @Override
    public void set(String treePath, T data) {
        Node<T> node = get(treePath);
        checkNode(node);
        node.data = data;
    }

    @Override
    public boolean insert(T data) {
        checkInsertData(data);
        return insert(new Node<>(data));
    }

    @Override
    public boolean remove(T data) {
        Node<T> node = search(this.root, data);
        return node != null && remove(node);
    }

    @Override
    public T remove(TreePath treePath) {
        Node<T> node = get(treePath);
        checkNode(node);
        T data = node.data;
        remove(node);
        return data;
    }

    @Override
    public T remove(String treePath) {
        Node<T> node = get(treePath);
        checkNode(node);
        T data = node.data;
        remove(node);
        return data;
    }

    @Override
    public boolean contains(T data) {
        return search(this.root, data) != null;
    }

    @Override
    public void clear() {
        clear(this.root);
        this.root = null;
        this.size = 0;
    }

    @Override
    public TreeVisitor<T> treeVisitor() {
        return new TreeVisitorImpl();
    }

    protected void checkInsertData(T data) {
        if (data == null) {
            throw new InvalidParamException("the data to be insert shouldn't be null");
        }
    }

    protected void checkNode(Node<T> node) {
        if (node == null) {
            throw new NoSuchElementException();
        }
    }

    protected Node<T> newNode(T data) {
        return new Node<>(data);
    }

    protected abstract int size(Node<T> node);

    protected abstract int height(Node<T> node);

    protected abstract Node<T> parentOf(Node<T> node);

    protected abstract Node<T> search(Node<T> node, T data);

    protected abstract Node<T> get(TreePath treePath);

    protected abstract Node<T> get(String treePath);

    protected abstract Node<T> getForInsert(TreePath treePath);

    protected abstract Node<T> getForInsert(String treePath);

    protected abstract boolean insert(Node<T> node);

    protected abstract boolean remove(Node<T> node);

    protected abstract boolean remove(Node<T> node, Node<T> parent);

    protected abstract void clear(Node<T> node);

    protected class TreeVisitorImpl implements TreeVisitor<T> {
        Node<T> current = root;
        Stack<Node<T>> stack = new QueueList<>();

        @Override
        public boolean exist() {
            return current != null;
        }

        @Override
        public boolean existLeft() {
            return current != null && current.left != null;
        }

        @Override
        public boolean existRight() {
            return current != null && current.right != null;
        }

        @Override
        public boolean existParent() {
            return !stack.isEmpty();
        }

        @Override
        public T get() {
            checkCurrentNode();
            return current.data;
        }

        @Override
        public T getLeft() {
            if (current != null && current.left != null) {
                return current.left.data;
            }
            return null;
        }

        @Override
        public T getRight() {
            if (current != null && current.right != null) {
                return current.right.data;
            }
            return null;
        }

        @Override
        public void left() {
            checkCurrentNode();
            stack.push(current);
            current = current.left;
        }

        @Override
        public void right() {
            checkCurrentNode();
            stack.push(current);
            current = current.right;
        }

        @Override
        public void leftNotRecord() {
            checkCurrentNode();
            current = current.left;
        }

        @Override
        public void rightNotRecord() {
            checkCurrentNode();
            current = current.right;
        }

        @Override
        public T leftAndGet() {
            left();
            checkCurrentNode();
            return current.data;
        }

        @Override
        public T rightAndGet() {
            right();
            checkCurrentNode();
            return current.data;
        }

        @Override
        public int height() {
            return stack.length() + 1;
        }

        @Override
        public boolean stepBack() {
            if (!stack.isEmpty()) {
                current = stack.pop();
                return true;
            }
            current = null;
            return false;
        }

        @Override
        public boolean stepBackNotPop() {
            if (!stack.isEmpty()) {
                current = stack.peek();
                return true;
            }
            current = null;
            return false;
        }

        @Override
        public boolean stepBack(int steps) {
            if (stack.length() >= steps) {
                while (steps > 0) {
                    current = stack.pop();
                    steps--;
                }
                return true;
            }
            return false;
        }

        @Override
        public void reset() {
            current = root;
            ((QueueList<T>) stack).clear();
        }

        protected void checkCurrentNode() {
            if (current == null) {
                throw new NoSuchElementException("current node doesn't exists");
            }
        }
    }
}